// i is 0-based

inline int Parent(int i) { 
  //return ((i + 1) / 2) - 1; 
  return (i - 1) >> 1;
}

inline int Left(int i) {
  // return (i + 1) * 2 - 1
  return (i << 1) + 1;
}

// min heap

void SiftUp(int A[], int i) {
  while (i > 0) {
    int p = Parent(i);
    if (A[i] < A[p]) std::swap(A[i], A[p]);
    else break;
    i = p;
  }
}

void SiftDown(int A[], int n, int p) {
  for (int k = Left(p); k < n; p = k, k = Left(p)) {
    if (k + 1 < n && A[k] > A[k + 1]) ++k;
    if (A[k] < A[p]) std::swap(A[k], A[p]);
    else break;
  }
}

void BuildHeap(int A[], int n) {
  for (int p = n / 2; p >= 0; --p)
    SiftDown(A, n, p);
}


